//给定一个非空的字符串
// s ，检查是否可以通过由它的一个子串重复多次构成。 
//
// 
//
// 示例 1: 
//
// 
//输入: s = "abab"
//输出: true
//解释: 可由子串 "ab" 重复两次构成。
// 
//
// 示例 2: 
//
// 
//输入: s = "aba"
//输出: false
// 
//
// 示例 3: 
//
// 
//输入: s = "abcabcabcabc"
//输出: true
//解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
// 
//
// 
//
// 提示： 
//
// 
// 
//
// 
// 1 <= s.length <= 10⁴ 
// s 由小写英文字母组成 
// 
//
// Related Topics 字符串 字符串匹配 👍 1205 👎 0


import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution459 {
    public boolean repeatedSubstringPattern(String s) {
         int[] next = new int[s.length()];
         nextArr(next, s);
         int len = s.length() - next[s.length() - 1];
         return next[s.length() - 1] != 0 && s.length() % len == 0;
    }

    private void nextArr(int[] next, String s) {
        char[] charArray = s.toCharArray();
        int j=0;
        next[0] = 0;
        for (int i = 1; i < charArray.length; i++) {
            while(j>0 && charArray[i] != charArray[j]) {
                j = next[j-1];
            }
            if(charArray[i] == charArray[j]) {
                j++;
            }
            next[i] = j;
        }
    }

    public static void main(String[] args) {
//        Solution459 solution459 = new Solution459();
//        String s="aba";
//        int[] next = new int[s.length()];
//        solution459.nextArr(next, s);
//        System.out.println(Arrays.toString(next));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
